#!/usr/bin/python
# -*- coding:utf-8 -*-
#堆排序
#@author: wklken@yeah.net

#先实现一个最大堆
class MaxHeap:
    
    def __init__(self):
        self.heap = [0]
    def isEmpty(self):
        return len(self.heap) == 1
    def size(self):
        return len(self.heap) - 1
    
    def insert(self, value):
        i = len(self.heap)
        self.heap.append(value)
        while i != 1 and value > self.heap[i/2]:
            self.heap[i], self.heap[i/2] = self.heap[i/2], self.heap[i]
            i = i/2
        self.heap[i] = value
        
    def deleteMax(self):
        if self.isEmpty(): #没有元素了
            return None
        
        x = self.heap[1]  #最大
        
        last = self.heap.pop()
        if self.size() == 0: #每次取最后一个，若是只剩两个的情况，pop
            return x
      
        i = 1
        ci = 2
        current_size = self.size()
        while  ci <= current_size:
            if ci < current_size and self.heap[ci] < self.heap[ci+1]:
                ci += 1
            
            if last >= self.heap[ci]:
                break
            
            self.heap[i] = self.heap[ci]
            i = ci
            ci *= 2
        self.heap[i] = last
        return x
    
    def initFromList(self, l):
        self.heap.extend(l)
        size = self.size()
        #从最后一棵子树开始，调整每一棵子树
        for i in range(size/2,0,-1):
              t_root = self.heap[i]

              c = 2*i
              while c <= size:
                  if c < size and self.heap[c] < self.heap[c+1]:
                      c += 1
                  if t_root >= self.heap[c]:
                      break
                  self.heap[c/2] = self.heap[c]
                  c *= 2
                  self.heap[c/2] = t_root

def heap_sort(l):
    m = MaxHeap()
    m.initFromList(l)
    result = []
    for i in range(len(l)):
        result.append(m.deleteMax())
        print result
    return result    
 
l = [1,5,2,11,7,8,9,22,0,44,12]
heap_sort(l)



    